package leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个二叉树，返回它的 前序 遍历。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,null,2,3]
 * 1
 * \
 * 2
 * /
 * 3
 * <p>
 * 输出: [1,2,3]
 * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 */
public class Solution3 {

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            result.add(root.val);
            result.addAll(preorderTraversal(root.left));
            result.addAll(preorderTraversal(root.right));
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode root_left = new TreeNode(9);
        TreeNode root_right = new TreeNode(20);
        TreeNode root_right_left = new TreeNode(15);
        TreeNode root_right_right = new TreeNode(7);
        root.left = root_left;
        root.right = root_right;
        root_right.left = root_right_left;
        root_right.right = root_right_right;
        System.out.println(new Solution3().preorderTraversal(root));
    }
}